package data.model;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * Implement the task graph as an list of tasks (vertices) each of which will have adjacency sets
 *  of outgoing and incoming edges.
 * Include methods for access (dfs), addition, removal, and checking for cycles.
 * 
 * @author Will Home
 *
 */
public class TaskGraph implements Iterable
{

	/** first and last vertices in list */
	protected static TaskGraph.Vertex first, last;
	
	private static int size = 0;
	
	private static Tarjan t;
	
	/**
	 * constructor
	 */
	public TaskGraph()
	{
		first = null;
		last = null;
		t = new Tarjan();
	}
	
	/**
	 * 
	 * @return Array of current tasks
	 */
	public static Task[] getTaskArray()
	{
		Task[] tar = new Task[size];
		TaskGraph.Vertex curr = last;
		if(last != null)
		{
			for(int i = 0; i < size; i++)
			{
				tar[i] = curr.element;
				curr = curr.pred;
			}
		}
		return tar;
		
	}

	/**
	 * check whether a task is in the task graph and if so, return it
	 * 
	 * @param taskName
	 * @return specified task
	 */
	public static Task getTask(String taskName)
	{
		//linear search of dll order n
		TaskGraph.Vertex curr = first;
		while(curr != null)
		{
			if(taskName.equals(curr.element.getTaskName()))
				return curr.element;
			else
				curr = curr.succ;
		}
		
		return null;
	}
	
	/**
	 * check whether a task is in the task graph and if so, return it
	 * 
	 * @param taskID
	 * @return specified task
	 */
	public static Task getTask(int taskID)
	{
		//linear search of dll order n
		TaskGraph.Vertex curr = first;
		while(curr != null)
		{
			if(taskID == (curr.element.getTaskID()))
				return curr.element;
			else
				curr = curr.succ;
		}
		
		return null;
	}

	/**
	 * get the set of tasks upon which this depends
	 * 
	 * @param taskName
	 * @return set of vertices of tasks upon which this depends
	 */
	public static TreeSet<Vertex> getDependencies(String taskName)
	{
		//linear search
		TaskGraph.Vertex curr = first;
		while(curr != null)
		{
			if(taskName.equals(curr.element.getTaskName()))
				return curr.inAdjSet;
			else
				curr = curr.succ;
		}
		
		return null;
	}
	
	/**
	 * get the set of tasks upon which this depends
	 * 
	 * @param taskID
	 * @return set of vertices of tasks upon which this depends
	 */
	public static TreeSet<Vertex> getDependencies(int taskID)
	{
		//linear search
		TaskGraph.Vertex curr = first;
		while(curr != null)
		{
			if(taskID == (curr.element.getTaskID()))
				return curr.inAdjSet;
			else
				curr = curr.succ;
		}
		
		return null;
	}
	
	/**
	 * get the set of tasks that depend on this
	 * 
	 * @param taskName
	 * @return set of vertices of tasks that depend on this
	 */
	public static TreeSet<Vertex> getDependants(String taskName)
	{
		//linear search
		TaskGraph.Vertex curr = first;
		while(curr != null)
		{
			if(taskName.equals(curr.element.getTaskName()))
				return curr.outAdjSet;
			else
				curr = curr.succ;
		}
		
		return null;
	}
	
	/**
	 * get the set of tasks that depend on this
	 * 
	 * @param taskID
	 * @return set of vertices of tasks that depend on this
	 */
	public static TreeSet<Vertex> getDependants(int taskID)
	{
		//linear search
		TaskGraph.Vertex curr = first;
		while(curr != null)
		{
			if(taskID == (curr.element.getTaskID()))
				return curr.outAdjSet;
			else
				curr = curr.succ;
		}
		
		return null;
	}

	/**
	 * adds a new task to the graph
	 * 
	 * @param name - new task name
	 * @return success check
	 */
	public static boolean addTask(String name) {
		
		TaskGraph.Vertex add = new Vertex(new Task(name), null, null);
		
		if (first == null && last == null) //list is empty
		{
			first = add;
			last = add;
			size++;
			
			return true; //success
		}
		//add tasks to the front
		else
		{
			first.pred = add;
			add.succ = first;
			first = add;
			size++;
			
			return true; //success
		}
	}

	/**
	 * Add a new dependency (directed edge) from the needed task to the dependent task
	 * 
	 * @param srcName task that is needed (source)
	 * @param destName dependent task (destination)
	 * @return success check
	 */
	public static boolean addDep(String srcName, String destName) {
		TaskGraph.Vertex curr = first;
		TaskGraph.Vertex src = null; //source of edge
		TaskGraph.Vertex dest = null; //destination of edge
		
		while(curr != null)
		{
			if(srcName.equals(curr.element.getTaskName()))
				src = curr;
			if(destName.equals(curr.element.getTaskName()))
				dest = curr;	
			if(src != null && dest != null)
			{
				return src.outAdjSet.add(dest) //create out-edge
						&& dest.inAdjSet.add(src); // create in-edge
			}
			else
				curr = curr.succ; // go to next vertex
		}
		
		return false;
	}
	
	/**
	 * Add a new dependency (directed edge) from the needed task to the dependent task
	 * 
	 * @param srcID task that is needed (source)
	 * @param destID dependent task (destination)
	 * @return success check
	 */
	public static boolean addDep(int srcID, int destID) {
		TaskGraph.Vertex curr = first;
		TaskGraph.Vertex src = null; //source of edge
		TaskGraph.Vertex dest = null; //destination of edge
		
		while(curr != null)
		{
			if(srcID == curr.element.getTaskID())
				src = curr;
			if(destID == curr.element.getTaskID())
				dest = curr;	
			if(src != null && dest != null)
			{
				boolean check = src.outAdjSet.add(dest) && dest.inAdjSet.add(src); // create in-edge & create out-edge
				return check;
			}
			else
				curr = curr.succ; // go to next vertex
		}
		
		return false;
	}
	
	/**
	 * Remove a task from the task graph, either adding its dependency set to tasks which are dependent on it,
	 *  or removing it completely
	 * 
	 * @param taskName task to be removed
	 * @param fuseDeps true if dependecies will be fused
	 * @return success check
	 */
	public static boolean removeTask(int taskID, boolean fuseDeps) {
		//linear search
		TaskGraph.Vertex curr = first;
		TreeSet<Vertex> currSet = null;
		
		while(curr != null)
		{
			if(taskID == (curr.element.getTaskID()))
			{
				//removes all edges connected to this task
				if(!fuseDeps)
				{
					//iterate over in adjacency set and remove task from out adjacency set of each vertex within
					Iterator<Vertex> inIt = curr.inAdjSet.iterator();
					
					while(inIt.hasNext())
					{
						 inIt.next().outAdjSet.remove(curr); //remove taskName
					}
					
					//iterate over out adjacency set and remove task from in adjacency set of each vertex within
					Iterator<Vertex> outIt = curr.outAdjSet.iterator();
					
					while(outIt.hasNext())
					{
						 outIt.next().inAdjSet.remove(curr); //remove taskName
					}
					
				}
				else
				{
					//add the outAdjSet to that of each vertex in the inAdjSet
					// and vice versa.
					
					currSet = curr.outAdjSet;
					
					Iterator<Vertex> it = curr.inAdjSet.iterator();
					
					while(it.hasNext())
					{
						it.next().outAdjSet.addAll(currSet);
					}
					
					currSet = curr.inAdjSet;
					
					it = curr.outAdjSet.iterator();
					
					while(it.hasNext())
					{
						it.next().inAdjSet.addAll(currSet);
					}
					
				}
				
				//bypass vertex - removes task and its adjacency sets
				if(curr.equals(first) && curr.equals(last))
				{
					curr = null;
				}
				else if(curr.equals(first))
				{
					first = curr.succ;
					curr.succ.pred = null;
				}
				else if (curr.equals(last))
				{
					curr.pred.succ = null;
					last = curr.pred;
				}
				else
				{
					curr.pred.succ = curr.succ;
					curr.succ.pred = curr.pred;
				}
				size--;
				return true;
			}
			else
				curr = curr.succ; // go to next vertex
		}

		return false;
	}

	/**
	 * Remove a task from the task graph, either adding its dependency set to tasks which are dependent on it,
	 *  or removing it completely
	 * 
	 * @param taskID task to be removed
	 * @param fuseDeps true if dependecies will be fused
	 * @return success check
	 */
	public static boolean removeTask(String taskName, boolean fuseDeps) {
		//linear search
				TaskGraph.Vertex curr = first;
				TreeSet<Vertex> currSet = null;
				
				while(curr != null)
				{
					if(taskName.equals(curr.element.getTaskName()))
					{
						//removes all edges connected to this task
						if(!fuseDeps)
						{
							//iterate over in adjacency set and remove task from out adjacency set of each vertex within
							Iterator<Vertex> inIt = curr.inAdjSet.iterator();
							
							while(inIt.hasNext())
							{
								 inIt.next().outAdjSet.remove(curr); //remove taskName
							}
							
							//iterate over out adjacency set and remove task from in adjacency set of each vertex within
							Iterator<Vertex> outIt = curr.outAdjSet.iterator();
							
							while(outIt.hasNext())
							{
								 outIt.next().inAdjSet.remove(curr); //remove taskName
							}
							
						}
						else
						{
							//add the outAdjSet to that of each vertex in the inAdjSet
							// and vice versa.
							
							currSet = curr.outAdjSet;
							
							Iterator<Vertex> it = curr.inAdjSet.iterator();
							
							while(it.hasNext())
							{
								it.next().outAdjSet.addAll(currSet);
							}
							
							currSet = curr.inAdjSet;
							
							it = curr.outAdjSet.iterator();
							
							while(it.hasNext())
							{
								it.next().inAdjSet.addAll(currSet);
							}
							
						}
						
						//bypass vertex - removes task and its adjacency sets
						if(curr.equals(first) && curr.equals(last))
						{
							curr = null;
						}
						else if(curr.equals(first))
						{
							first = curr.succ;
							curr.succ.pred = null;
						}
						else if (curr.equals(last))
						{
							curr.pred.succ = null;
							last = curr.pred;
						}
						else
						{
							curr.pred.succ = curr.succ;
							curr.succ.pred = curr.pred;
						}
						size--;
						return true;
					}
					else
						curr = curr.succ; // go to next vertex
				}

				return false;
	}
	
	/**
	 * Remove a dependency (directed edge)  from the needed task to the dependent task
	 * 
	 * @param srcName task that is needed (source)
	 * @param destName dependent task (destination)
	 * @return success check
	 */
	public static boolean removeDep(String srcName, String destName) {
		//linear search
		TaskGraph.Vertex curr = first;
		TaskGraph.Vertex subCurr = null;
		while(curr != null)
		{
			//find destination
			if(destName.equals(curr.element.getTaskName()))
			{
				//create iterator over in adjacency set
				Iterator<Vertex> it = curr.inAdjSet.iterator();
				
				while(it.hasNext())
				{
					curr = it.next();
					//find source
					if(curr.element.getTaskName().equals(srcName))
					{
						//remove destination from out adjacency set of source
						
						Iterator<Vertex> subIt = curr.outAdjSet.iterator();
						
						while(subIt.hasNext())
						{
							subCurr = it.next();
							if(subCurr.element.getTaskName().equals(destName))
								subIt.remove();
						}
						
						//remove source from in adjacency set of destination
						it.remove();
						return true;
					}
				}
				
				return false;
			}
			
			//find source
			else if(srcName.equals(curr.element.getTaskName()))
			{
				//create iterator over out adjacency set
				Iterator<Vertex> it = curr.outAdjSet.iterator();
				
				while(it.hasNext())
				{
					curr = it.next();
					//find destination
					if(curr.element.getTaskName().equals(destName))
					{
						//remove source from in adjacency set of destination
						
						Iterator<Vertex> subIt = curr.inAdjSet.iterator();
						
						while(subIt.hasNext())
						{
							subCurr = it.next();
							if(subCurr.element.getTaskName().equals(srcName))
								subIt.remove();
						}
						
						//remove destination from out adjacency set of source
						it.remove();
						return true;
					}
				}
				
				return false;
			}
			else
				curr = curr.succ; //go to next vertex
		}

		return false;
	}
	
	/**
	 * Remove a dependency (directed edge)  from the needed task to the dependent task
	 * 
	 * @param srcID task that is needed (source)
	 * @param destID dependent task (destination)
	 * @return success check
	 */
	public static boolean removeDep(int srcID, int destID) {
		//linear search
		TaskGraph.Vertex curr = first;
		TaskGraph.Vertex subCurr = null;
		while(curr != null)
		{
			//find destination
			if(destID == curr.element.getTaskID())
			{
				//create iterator over in adjacency set
				Iterator<Vertex> it = curr.inAdjSet.iterator();
				
				while(it.hasNext())
				{
					curr = it.next();
					//find source
					if(srcID == curr.element.getTaskID())
					{
						//remove destination from out adjacency set of source
						
						Iterator<Vertex> subIt = curr.outAdjSet.iterator();
						
						while(subIt.hasNext())
						{
							subCurr = subIt.next();
							if(subCurr.element.getTaskID() == destID)
								subIt.remove();
						}
						
						//remove source from in adjacency set of destination
						it.remove();
						return true;
					}
				}
				
				return false;
			}
			
			//find source
			else if(srcID == curr.element.getTaskID())
			{
				//create iterator over out adjacency set
				Iterator<Vertex> it = curr.outAdjSet.iterator();
				
				while(it.hasNext())
				{
					curr = it.next();
					//find destination
					if(destID == curr.element.getTaskID())
					{
						//remove source from in adjacency set of destination
						
						Iterator<Vertex> subIt = curr.inAdjSet.iterator();
						
						while(subIt.hasNext())
						{
							subCurr = subIt.next();
							if(subCurr.element.getTaskID() == srcID)
								subIt.remove();
						}
						
						//remove destination from out adjacency set of source
						it.remove();
						return true;
					}
				}
				
				return false;
			}
			else
				curr = curr.succ; //go to next vertex
		}

		return false;
	}
	
	/**
	 * Remove all tasks
	 */
	public static void clear()
	{
		first = null;
		last = null;
		size = 0;
	}
	
	/**
	 * Gets the Task IDs of the root elements of the task graph
	 * 
	 * @return array of taskIDs
	 */
	public static ArrayList<Integer> getRoots()
	{
		ArrayList<Integer> roots = new ArrayList<Integer>();
		
		Vertex curr = first;
		while(curr != null)
		{
			if(curr.inAdjSet.isEmpty())
			{
				roots.add(curr.element.getTaskID());
			}
			curr = curr.succ;
		}
		
		return roots;
	}

	/**
	 * Check that the task graph is acyclic
	 * 
	 * @return true if acyclic
	 */
	public static boolean checkAcyclic() {

		ArrayList<ArrayList<Task>> sccList = t.executeTarjan();
		boolean check = true;
		
		//check size of each scc in sccList
		for(ArrayList<Task> scc : sccList)
		{
			//if size > 1 cycle so print
			if(scc.size() > 1)
			{
				for(Task t : scc)
				{
					System.out.print(t.getTaskName() + ", ");
					
				}
				System.out.println();
				check = false;
			}
		}
		
		return check;
	}
	
	protected static void clearIndices()
	{
		TaskGraph.Vertex curr = first;
		while(curr != null)
		{
			curr.index = -1;
			curr.lowlink = -1;
			curr = curr.succ;
		}

	}
	

	/**
	 * Vertex of task graph as a component of a dll.
	 * Also contains adjacency set and indices for Tarjan's
	 * 
	 * @author Will Home
	 *
	 */
	public static class Vertex implements Comparable<Vertex>
	{	 
		protected Task element;	
		protected Vertex pred, succ;
		protected TreeSet<Vertex> inAdjSet; 
		protected TreeSet<Vertex> outAdjSet;
		
		/** Strong connectivity source for Tarjan's */
		protected int index = -1;
		
		/** lowlink source for Tarjan's */
		protected int lowlink = -1;
		
		protected boolean visited = false;
		
		public Vertex (Task elem, Vertex pred, Vertex succ)
		{			
			this.element = elem;
			this.pred = pred; this.succ = succ;
			inAdjSet = new TreeSet<Vertex>();
			outAdjSet = new TreeSet<Vertex>();
		}
				
		public Task getElem()
		{
			return element;
		}

		@Override
		public int compareTo(Vertex other) {
			return this.element.compareTo(other.element);
		}
	}

@Override
public Iterator iterator() {
	return new VtxIterator();
}

private class VtxIterator implements Iterator<Vertex>
{
	private Vertex curr = first;

	@Override
	public boolean hasNext() {
		if(curr.succ == null)
			return false;
		else
			return true;
	}

	@Override
	public Vertex next() {
		curr = curr.succ;
		return curr;
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub
		
	}
}

 class Tarjan {
	
	private int index = 0;
	
	private ArrayDeque<Vertex> stack = new ArrayDeque<Vertex>();
	
	private ArrayList<ArrayList<Task>> SCCList = new ArrayList<ArrayList<Task>>();
	
	protected ArrayList<ArrayList<Task>> executeTarjan()
	{
		SCCList.clear();
		stack.clear();
		clearIndices();
		index = 0;
		
		Vertex curr = first;
		while(curr != null)
		{
			if(curr.index == -1)
			{
				tarjan(curr);
			}
			curr = curr.succ;
		}
		
		//System.out.println("Tarjan done");
		return SCCList;
		
	}

	private void tarjan(Vertex v) {
		
		//System.out.println("Tarjan " + v.element.getTaskName() );
		
		v.index = index;
		v.lowlink = index;
		index++;
		
		stack.push(v);
		
		Iterator<Vertex> it = v.outAdjSet.iterator();
		
		while(it.hasNext())
		{
			Vertex w = (Vertex) it.next();
			
			if(w.index == -1)
			{
				tarjan(w);
				v.lowlink = Math.min(v.lowlink, w.lowlink);
			}
			else if(stack.contains(w))
			{
				v.lowlink  = Math.min(v.lowlink, w.index);
			}
		}

		if(v.lowlink == v.index) //root of scc
		{
			Vertex w;
			ArrayList<Task> component = new ArrayList<Task>(1);
			do
			{
				w = stack.pop();
				component.add(w.element);
			}
			while(w != v);

			SCCList.add(component);
		}
	}

 }

}
